#include <stdio.h>
#include <string.h>
int arr[1005];
int pre[1005];

int find(int x)
{
    int r=x;
    while(pre[r]!=r)
    r=pre[r];
    int i=x,j;
    while(i!=r)
    {
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;
}

void join(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a!=b)
    {
        pre[a]=b;
    }
}



int main()
{

        int m, n, a, b;
        scanf("%d%d", &m, &n);
        for(int i=1;i<=m;i++)
        {
            pre[i]=i;

        }
        memset(arr, 0, sizeof(arr));
        for(int i = 0; i < n; ++i)
        {
            scanf("%d%d", &a, &b);
            
            if(find(a) != find(b))
            {
                join(a,b);
            }
            
            if(arr[a] != 0){
                ++arr[a];
            }else{
                arr[a] = 1;
            }
            if(arr[b] != 0){
                ++arr[b];
            }else{
                arr[b] = 1;
            }
        }
       
        int tag = 1;
        for(int i = 1; i <= m; ++i){
            if(arr[i] % 2 != 0){
                tag = 0;
                break;
            }
        }
        if(tag)
        {
           
            int cnt = 0;
            for(int i = 1; i <= m; ++i)
            {
                if(pre[i] == i)
                {
                    ++cnt;
                }
            }
            if(cnt == 1)
            {
                printf("1");
            }
            else
            {
                    printf("0");
            }
        }
        else
        {
            printf("0");
        }
        return 0;
}